## Variations

### 0/1 knapsack problem
> TODO: Describe the [dynamic programming](Dynamic programming) approach
> TODO: Describe the [meet-in-the-middle](Meet-in-the-middle) approach

### Bounded knapsack problem
> TODO: Describe $O(\log W)$ reduction from bounded knapsack to 0/1 knapsack (only works when optimizing?) [^1] [^2]

### Unbounded knapsack problem
Unbounded knapsack can be reduced to 0/1 knapsack in a similar manner as [bounded knapsack](#bounded-knapsack-problem).

### Fractional knapsack problem
> TODO: Describe [greedy algorithm](Greedy algorithm)

## Problems
- [Knapsack](https://open.kattis.com/problems/knapsack)
- [Walrus Weights](https://open.kattis.com/problems/walrusweights)
- [Roller coaster fun](https://open.kattis.com/problems/rollercoasterfun)
- [Tug of War](https://boi.cses.fi/files/boi2015_day2.pdf)
- [Buffed Buffet](https://open.kattis.com/problems/buffet)
- [Lucky Country](http://codeforces.com/problemset/problem/95/E) [^3]

## See also
- [NP-complete]()
- [Frobenius coin problem]()

## External links
- [Continuous knapsack problem](https://en.wikipedia.org/wiki/Continuous_knapsack_problem)

[^1]: <http://petr-mitrichev.blogspot.com/2011/07/integral-bounded-knapsack-problem.html>
[^2]: <http://dhruvbird.blogspot.is/2011/09/integer-01-bounded-knapsack-problem.html>
[^3]: <http://codeforces.com/blog/entry/2257>